
// 二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。
// 二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，
// 在右侧节点存储（比父节点）大（或者等于）的值。上一节的图中就展现了一棵二叉搜索树。

// insert(key)：向树中插入一个新的键。
// search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回false。
// inOrderTraverse：通过中序遍历方式遍历所有节点。
// preOrderTraverse：通过先序遍历方式遍历所有节点。
// postOrderTraverse：通过后序遍历方式遍历所有节点。
// min：返回树中最小的值/键。
// max：返回树中最大的值/键。
// remove(key)：从树中移除某个键。

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null
  }

  insert(key) {
    const newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    // 新节点在参照节点的左边
    if (newNode.key < node.key) {
      // 参照节点左边不存在，则直接插入
      if (node.left === null) {
        node.left = newNode;
      } else {
        // 继续往下找
        this.insertNode(node.left, newNode);
      }
    } else {
    // 新节点在参照节点的右边
      if (node.right === null) {
        // 参照节点右边不存在,则直接插入
        node.right = newNode;
      } else {
        // 继续往下找
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 中序遍历
  // 中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。
  // 中序遍历的一种应用就是对树进行排序操作。
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }

  inOrderTraverseNode(node, callback) {
    if (node !== null) {
      // 先一直往左边找，找到最小的为止
      this.inOrderTraverseNode(node.left, callback);
      // 走完之后，运行回调函数，此时打印出来的就是最小值
      callback(node.key);
      // 在去右边找，如果有，重复上面的步骤，找到最小的为止
      this.inOrderTraverseNode(node.right, callback);
    }
  }

  // 先序遍历
  // 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。
  preOrderTraverse(callback) {
   this.preOrderTraverseNode(this.root, callback);
  }

  preOrderTraverseNode(node, callback) {
    if (node !== null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }

  // 后序遍历
  // 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小。
  // 后序遍历会先访问左侧子节点，然后是右侧子节点，最后是父节点本身。
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  postOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }

  min() {
    return this.minNode(this.root);
  }

  minNode(node) {
   if (node === null) {
     return null
   }
   // 一直找到最左边
   while(node && node.left) {
     node = node.left;
   }
   return node.key;
  }

  max() {
    return this.maxNode(this.root);
  }

  maxNode(node) {
    if (node === null) {
      return null
    }
    // 一直找到最右边
    while(node && node.right) {
      node = node.right;
    }
    return node.key;
  }

  search(key) {
    return this.searchNode(this.root, key);
  }

  searchNode(node, key) {
    // 节点不存在 直接返回false
    if (node === null) {
      return false;
    }
    // 当前要找的值在节点左边
    if (node.key > key) {
      return this.searchNode(node.left, key);
    } else if (node.key < key) {
    // 当前的值在节点右边  
      return this.searchNode(node.right, key);
    } else {
    // 相等 直接返回treu  
      return true;
    }
  }

  remove(key) {
    // 移除一个节点
    this.removeNode(this.root, key);
  }

  removeNode(node, key) {
    // 如果节点不存在 直接返回
    if (node === null) {
      return null;
    }
    // 当前要移除的key 小于节点的key，说明要移除的key在节点的左边
    if (key < node.key) {
      // 左边需要继续递归查找
      node.left = this.removeNode(node.left, key);
      return node;
    }
    // 当前要移除的key 大于节点的key，说明要移除的key在节点的右边
    else if (key > node.key) {
      // 右边继续查找
      node.right = this.removeNode(node.right, key);
      return node;
    } else {
      // key相同，找到了要移除的node
      // 第一种情况，一个叶节点
      if (node.left === null && node.right === null) {
        // 移除一个叶节点，直接将该节点设置为null
        node = null;
        // 返回null,修改父节点对子节点的指针
        return node;
      }
      // 第二种，只有一个子节点的
      if (node.left === null) {
        // 左边没有，说明是只有右节点，直接把右节点赋值给父节点
        node = node.right;
        // 返回当前的节点
        return node;
      } else if (node.right === null) {
        // 右边没有，说明是只有左节点，直接把左节点赋值给父节点
        node = node.left;
        // 返回当前的节点
        return node;
      }
      // 第三种， 有两个子节点
      // 要移除当前节点，就需要找个节点去代替，这时从该节点的右边找到最小的那个
      const aux = this.findMinNode(node.right);
      // 找到当前节点右边最小的节点替换
      node.key = aux.key;
      // 替换后 需要删除之前的节点，否则节点重复了
      node.right = this.removeNode(node.right, aux.key);
      // 更新父节点的指向
      return node;
    }
  }

  // 查找节点的最小值，返回最小的节点
  findMinNode(node) {
    while(node && node.left) {
      node = node.left;
    }
    return node;
  }
}

const tree = new BinarySearchTree();

tree.insert(10);
tree.insert(15);
tree.insert(6);
tree.insert(8);
tree.insert(13);
tree.insert(17);
tree.insert(7);
tree.insert(12);
tree.insert(5);
tree.insert(18);
tree.insert(9);
tree.insert(4);
tree.insert(14);
tree.insert(16);

/*
                    10
               /         \
              6           15
             / \       /    \
            5   8     13     17
           /   / \    / \    / \
          4   7   9  12  14 16  18
*/ 

function printNode(value) {
  console.log(value);
}

// tree.remove(15);

// tree.inOrderTraverse(printNode);   //  4 5 6 7 8 9 10 12 13 14 15 16 17 18

// tree.preOrderTraverse(printNode);  //  10 6 5 4 8 7 9 15 13 12 14 17 16 18

// tree.postOrderTraverse(printNode); //  4 5 7 9 8 6 12 14 13 16 18 17 15 10
